// 10.3 定制操作
/**
 * 很多算法都会比较输入序列中的元素。默认情况下，这类算法使用元素类型的<或==运算符完成比较。
 * 标准库还为这些算法定义了额外的版本，允许我们提供自己定义的操作来代替默认运算符。
 * 例如，sort算法默认使用元素类型的<运算符。但可能我们希望的排序顺序与<所定义的顺序不同，
 * 或是我们的序列可能保存的是未定义<运算符的元素类型（如Sales_data）。在这两种情况下，都需要重载sort的默认行为。
 */

#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array, std::stack, std::queue;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::begin, std::cbegin, std::end, std::cend, std::find, std::accumulate, std::equal, std::fill, std::fill_n, std::back_inserter;
using std::cin, std::cout, std::endl;
using std::copy, std::replace, std::replace_copy, std::sort, std::unique,std::stable_sort;

void elimDups(vector<string> &words);
bool isShorter(const string &s1, const string &s2);

int main()
{
    // 10.3.1 向算法传递函数
    // 作为一个例子，假定希望在调用elimDups（参见10.2.3节，第343页）后打印vector的内容。
    // 此外还假定希望单词按其长度排序，大小相同的再按字典序排列。
    // 为了按长度重排vector，我们将使用sort的第二个版本，此版本是重载过的，它接受第三个参数，此参数是一个谓词（predicate）。

    // 谓词
    // 谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类：
    // 一元谓词（unary predicate，意味着它们只接受单一参数）和二元谓词（binary predicate，意味着它们有两个参数）。
    vector<string> words{"abc","abcd","efg","hijk","abc"};
    sort(words.begin(), words.end(), isShorter); // 先按长度排序，长度相同的再按字典排序
    for (string s: words)
        cout << s << endl; // 输出abc efg abc abcd hijk

    // 排序算法
    // 为了保持相同长度的单词按字典序排列，可以使用stable_sort算法。这种稳定排序算法维持相等元素的原有顺序。
    vector<string> words1{"abc","abcd","efg","hijk","abc"};
    elimDups(words1);
    stable_sort(words1.begin(),words1.end(),isShorter);
    for (string s: words1)
        cout << s << endl; // 输出abc efg abcd hijk

    

    return 0;
}

void elimDups(vector<string> &words)
{
    // 按字典排序words，以便查找重复单词
    sort(words.begin(), words.end());
    // unique重排输入范围，使得每个单词只出现一次
    // 排列在范围的前部，返回指向不重复区域之后一个位置的迭代器
    auto end_unique = unique(words.begin(), words.end());
    // 使用向量操作erase删除重复单词
    words.erase(end_unique,words.end());
}

// 比较函数，用来按长度排序单词
bool isShorter(const string &s1, const string &s2)
{
    return s1.size() < s2.size();
}
